package main

import (
	"fmt"
	"math/rand"
	"time"
)

/*
稳定性:任意两个相等的数据, 排序前后的相对位置不发生改变
当你数据具有某种特征是, 这种算法可能是最好的
*/

//TODO : 交换排序 - 冒泡排序
/*
最好的情况 : T = O(N)
最坏的情况 : T = O(N^2)
稳定: 只有在一data[i] > data[j]是才会发生交换
 */
func BubbleSort(data []int, L int) {
	t := time.Now()
	for i := 0; i < L; i++ {
		for j := i + 1; j < L; j++ {
			if data[i] > data[j] {
				data[i], data[j] = data[j], data[i]
			}
		}
	}
	fmt.Println("BubbleSort - Time:", time.Since(t))
}

//TODO : 插入排序 - 直接插入排序
/*
最好的情况 : T = O(N)
最坏的情况 : T = O(N^2)
稳定
 */
func InsertionSort(data []int, L int) {
	t := time.Now()
	for i := 1; i < L; i++ {
		for j := i; j > 0 && data[i] < data[j-1]; j-- {
			data[j] = data[j-1]
			data[j] = data[i]
		}
	}
	fmt.Println("InsertionSort - Time:", time.Since(t))
}

//todo:前面两种算法 每次交换消除一个逆序对. 要提高算法的效率, 我们必须每次消除不止一个逆序对, 每次交换相隔较远的两个元素

//TODO : 插入排序 - 希尔排序 (希尔增量 L/2)
func ShellSort(data []int, L int) {
	t := time.Now()
	for i := L / 2; i > 0; i /= 2 { //增量
		for j := i; j < L; j ++ { //插入排序
			for k := j; k >= i && data[j] < data[k-i]; k -= i {
				data[k] = data[k-i]
				data[k] = data[j]
			}
		}
	}
	fmt.Println("ShellSort - Time:", time.Since(t))
}

// 增量元素不互质, 则小增量可以根本不起作用
//Hibbard增量：{1, 3, ..., 2^k-1}
/*
func ShellSort2(data []int, L int) {
	t := time.Now()
	for i := 1; i > ??? ; i /= 2 { //增量  int(math.Log2(float64(L/2+1)))
		for j := i; j < L; j ++ { //插入排序
			for k := j; k >= i && data[j] < data[k-i]; k -= i {
				data[k] = data[k-i]
				data[k] = data[j]
			}
		}
	}
	fmt.Println("ShellSort - Time:", time.Since(t), data)
}
*/

//TODO : 交换排序 - 快速排序
func QuickSort(data []int, L int) {
	if L <= 1 {
		return
	}

	mid := data[0]
	left, right := 0, L-1

	for i := 1; i <= right; {
		fmt.Println(mid)
		if mid < data[i] {
			data[i], data[right] = data[right], data[i]
			right --
		} else {
			data[i], data[left] = data[left], data[i]
			left++
			i++
		}
	}

	QuickSort(data[:left], len(data[:left]))
	QuickSort(data[left+1:], len(data[left+1:]))
}

func QuickSort2(data []int, L int) {
	t := time.Now()
	QuickSort(data, L)
	fmt.Println("QuickSort2 - Time:", time.Since(t))
}

func main() {

	rand.Seed(time.Now().Unix())
	number := make([]int, 10, 10000000)
	for k, _ := range number {
		number[k] = rand.Intn(100)
	}

	L := len(number)

	//fmt.Println(number)

	//交换排序 - 冒泡排序
	//BubbleSort(number, L)

	//插入排序 - 直接插入排序
	//InsertionSort(number, L)

	//插入排序 - 希尔排序
	//ShellSort(number, L)

	//交换排序 - 快速排序
	QuickSort2(number, L)
}
